1. Field
The subject matter herein relates generally to image processing. More particularly, the subject matter relates to performing efficient diffusion dithering using a filter whose weights are dyadic rationals, and applying the weights using one or more shift, add, or subtract operations.
2. Background
When an image is to be represented in a system that has a finite color palette, a color from the palette is selected to represent the color of the original image. Since a finite palette has gaps, the original image's true color may not correspond precisely to any color in the palette, so the selected color may be chosen by rounding the true color to a nearby color in the palette. To the extent that the selected color differs from the original image's true color, a rounding error is realized. Diffusion dithering can be used to distribute the error in the pixel to neighboring or nearby pixels, thereby reducing artifacts or other distortions that would otherwise be caused by the rounding errors.
Diffusion dithering is performed by applying a filter to the rounding error for a pixel and distributing the error according to a filter. The filter has a set of fractions called weights. To distribute a portion of the rounding error to other pixels, each of the weights in the filter is multiplied by the error, and the resulting products are distributed to particular pixels near the pixels whose color value is being rounded. Applying the fractional weights is normally performed using a series of multiply and divide operations or floating point arithmetic, which can be computationally-expensive.
Various filters have been experimentally determined to produce good image results, but many of these filters used fractional weights that are complicated to apply. For example, the Stucki filter uses fractions whose denominator is 42, and the Jarvis filter uses fractions whose denominator is 48. When the denominator is a power of two, the fraction can be applied to an error by multiplying the error by the numerator and then using a fast right-bit-shift operation to divide by the numerator. However, since 42 and 48 are not powers of two, applying fractions with these denominators involves using either a machine's division logic, or floating-point multiplication, both of which are computationally expensive. Moreover, applying the numerator in the fraction to the weight may involve a multiplication operation, which is not as efficient as a shift, add, or subtract operation. On a small device, such as a wireless handset or handheld computer, there may not be sufficient computational power to perform a diffusion dither at an acceptable speed using these expensive operations.